// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package flate

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func ( []literalNode) {
	 := len()
	quickSort(, 0, , maxDepth())
}

func ( []literalNode, , ,  int) {
	for - > 12 { // Use ShellSort for slices <= 12 elements
		if  == 0 {
			heapSort(, , )
			return
		}
		--
		,  := doPivot(, , )
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if - < - {
			(, , , )
			 =  // i.e., quickSort(data, mhi, b)
		} else {
			(, , , )
			 =  // i.e., quickSort(data, a, mlo)
		}
	}
	if - > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for  :=  + 6;  < ; ++ {
			if [].literal < [-6].literal {
				[], [-6] = [-6], []
			}
		}
		insertionSort(, , )
	}
}
func ( []literalNode, ,  int) {
	 := 
	 := 0
	 :=  - 

	// Build heap with greatest element at top.
	for  := ( - 1) / 2;  >= 0; -- {
		siftDown(, , , )
	}

	// Pop elements, largest first, into end of data.
	for  :=  - 1;  >= 0; -- {
		[], [+] = [+], []
		siftDown(, , , )
	}
}

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
func ( []literalNode, , ,  int) {
	 := 
	for {
		 := 2* + 1
		if  >=  {
			break
		}
		if +1 <  && [+].literal < [++1].literal {
			++
		}
		if [+].literal > [+].literal {
			return
		}
		[+], [+] = [+], [+]
		 = 
	}
}
func ( []literalNode, ,  int) (,  int) {
	 := int(uint(+) >> 1) // Written like this to avoid integer overflow.
	if - > 40 {
		// Tukey's ``Ninther,'' median of three medians of three.
		 := ( - ) / 8
		medianOfThree(, , +, +2*)
		medianOfThree(, , -, +)
		medianOfThree(, -1, -1-, -1-2*)
	}
	medianOfThree(, , , -1)

	// Invariants are:
	//	data[lo] = pivot (set up by ChoosePivot)
	//	data[lo < i < a] < pivot
	//	data[a <= i < b] <= pivot
	//	data[b <= i < c] unexamined
	//	data[c <= i < hi-1] > pivot
	//	data[hi-1] >= pivot
	 := 
	,  := +1, -1

	for ;  <  && [].literal < [].literal; ++ {
	}
	 := 
	for {
		for ;  <  && [].literal > [].literal; ++ { // data[b] <= pivot
		}
		for ;  <  && [].literal < [-1].literal; -- { // data[c-1] > pivot
		}
		if  >=  {
			break
		}
		// data[b] > pivot; data[c-1] <= pivot
		[], [-1] = [-1], []
		++
		--
	}
	// If hi-c<3 then there are duplicates (by property of median of nine).
	// Let's be a bit more conservative, and set border to 5.
	 := - < 5
	if ! && - < (-)/4 {
		// Lets test some points for equality to pivot
		 := 0
		if [].literal > [-1].literal { // data[hi-1] = pivot
			[], [-1] = [-1], []
			++
			++
		}
		if [-1].literal > [].literal { // data[b-1] = pivot
			--
			++
		}
		// m-lo = (hi-lo)/2 > 6
		// b-lo > (hi-lo)*3/4-1 > 8
		// ==> m < b ==> data[m] <= pivot
		if [].literal > [].literal { // data[m] = pivot
			[], [-1] = [-1], []
			--
			++
		}
		// if at least 2 points are equal to pivot, assume skewed distribution
		 =  > 1
	}
	if  {
		// Protect against a lot of duplicates
		// Add invariant:
		//	data[a <= i < b] unexamined
		//	data[b <= i < c] = pivot
		for {
			for ;  <  && [-1].literal > [].literal; -- { // data[b] == pivot
			}
			for ;  <  && [].literal < [].literal; ++ { // data[a] < pivot
			}
			if  >=  {
				break
			}
			// data[a] == pivot; data[b-1] < pivot
			[], [-1] = [-1], []
			++
			--
		}
	}
	// Swap pivot into middle
	[], [-1] = [-1], []
	return  - 1, 
}

// Insertion sort
func ( []literalNode, ,  int) {
	for  :=  + 1;  < ; ++ {
		for  := ;  >  && [].literal < [-1].literal; -- {
			[], [-1] = [-1], []
		}
	}
}

// maxDepth returns a threshold at which quicksort should switch
// to heapsort. It returns 2*ceil(lg(n+1)).
func ( int) int {
	var  int
	for  := ;  > 0;  >>= 1 {
		++
	}
	return  * 2
}

// medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
func ( []literalNode, , ,  int) {
	// sort 3 elements
	if [].literal < [].literal {
		[], [] = [], []
	}
	// data[m0] <= data[m1]
	if [].literal < [].literal {
		[], [] = [], []
		// data[m0] <= data[m2] && data[m1] < data[m2]
		if [].literal < [].literal {
			[], [] = [], []
		}
	}
	// now data[m0] <= data[m1] <= data[m2]
}